Wireless mesh networking is emerging as a promising technology to provide broadband Internet access. Generally speaking, a wireless mesh network is composed of a collection of mesh routers each serving as the access point for the mobile clients in its coverage range, while the mesh routers are interconnected with each other by wireless links forming a wireless ad hoc backbone. Some mesh routers have wired connections to the Internet and serve as the gateway between the mesh network and the Internet. Compared to traditional wireless LANs, the main feature of wireless mesh networks is their multi-hop wireless backbone infrastructure.
One of the key advantages of wireless mesh networks is that they provide an inexpensive, quick and easy solution to extend the existing wired networks to a wider area. Wireless mesh networks are usually built on the IEEE 802.11 technologies, but they can also be built upon other technologies such as IEEE 802.16 or Bluetooth. Well-known wireless mesh networks include MIT Roofnet, Seattle Wireless, and city-wide infrastructure mesh networks to be deployed in Philadelphia, San Francisco, and many other places to offer the Internet access to their residents, using commercial products from companies like Tropos, Cisco, and so on.
Wireless mesh networks, however, all face one significant challenge: they do not scale; the end-to-end throughput decreases dramatically with the increase of the number of mesh nodes primarily due to physical signal interference. To alleviate this problem, one simple approach is to equip each mesh router (abbreviated as node hereafter) with multiple radios (i.e., wireless interface cards) working on non-interfering channels. For example, there are twelve non-interfering channels in 802.11a and three in 802.11b/g according to the IEEE 802.11 specifications. Such networks are usually called multi-channel multi-radio mesh networks (abbreviated as MCMR mesh networks hereafter), while networks with one radio per node are called single-radio networks. In a single-radio network, all nodes have to tune their radios to one channel to keep the network connected. As a result, much of the available radio resources are wasted. In contrast, the radios in an MCMR mesh network can work on multiple channels simultaneously without interfering with each other, resulting in more efficient use of the radio resources. Consequently, the mesh network capacity can be improved if the non-interfering channels are appropriately assigned to the radios.
One of the key issues in the MCMR mesh networks is the channel assignment. The purpose of a channel assignment algorithm is to make efficient use of available radio spectrum resource with relatively few radios on each node (say 2-3 radios on each node and 12 non-interfering channels in 802.11a).
Existing channel assignment solutions for MCMR mesh networks can be classified into two categories: static channel assignment and dynamic channel assignment. Static channel assignment means that the channel setting of each radio lasts for a relatively long period of time from several minutes to even hours or days, while dynamic channel assignment means that the channel setting of each radio changes very frequently such as every several milliseconds.
Existing dynamic channel assignment solutions can be further classified into two categories: per-packet based and time-slot based. Per-packet based solutions mean that channel setting of a radio may change for each packet transmission, while the time-slot based solutions mean that channel setting of a radio will change on a fixed time slot such as every 10 ms.
Existing static channel assignment solutions can be further classified into three categories: identical-setting, topology-based and Joint decision of Channel Assignment and Routing (JCAR).
The identical-setting solution means that the channel setting of the radios on each node is the same, such as channel 1 for radio 1, channel 2 for radio 2, etc. Such solution is very simple and does not need any knowledge about the network topology and traffic patterns.
The topology-based solutions assume the topology is stable, which is the case of wireless mesh networks, and then define some metrics to measure the interference in the view of topology and try to minimize the given metrics. Representative metrics include the maximum number and average number of interfering links working on the same channel.
The JCAR solutions assume both the topology and end-to-end traffic pattern is stable, and then jointly determine the channel setting on each node and the routing between each pair of nodes. As the capacity of each link is affected by the channel assignment and the traffic of each link is determined by the end-to-end traffic demand and routing decisions, the JCAR solutions try to combine the channel assignment decision and routing decision so that the capacity and traffic of each link can be well matched.
The per-packet based dynamic channel assignment solutions require that the radio devices' channel switching time be much lower than its typical packet transmission time to justify their benefit. Otherwise the channel switching overhead will be prohibitively high. However, the channel switching time of existing commodity 802.11 network cards with existing Linux drivers is about 5 ms˜19 ms, while the transmission time for a 1000-byte packet via 802.11a is just 220 μs. In the future, the channel switching time is expected to be decreased to 150-200 μs, which is still too long for per-packet based channel switching.
For time-slot based dynamic channel assignment solutions, a packet may experience long delay on each routing node before it can be transmitted. If each node has six neighboring nodes (which is the case of cellular deployment) and the packet arrival satisfies the Poisson distribution, then the queuing delay of each packet on each routing node will be six times of the original queuing delay according to the queuing theory. The intuitive reason is that a single transmission queue is broken into a number of sub-queues which are served in the same time interval. As a result, the end-to-end delay of a multi-hop path may well exceed the requirement of real-time interactive applications such as VoIP. Furthermore, Such solution requires that the clocks of a lot of nodes (not just neighboring nodes) be strictly synchronized for channel switching actions, which will also cause considerable overhead. For example, suppose node B uses a same radio to communicate with node A and C on different time slots, and node C uses a same radio to communicate with node B and D, as shown in FIG. 1. Then the clocks on node A, B, C, and D should all be synchronized, although node A and D are not neighbors of each other.
In identical-setting static channel assignment solutions, the channel setting on each node is identical, so the system can just make use of x channels with x radios on each node. As the number of radios on each node is typically much smaller than the number of available channels (say 2-3 radios on each node and 12 available channels in 802.11a), this solution cannot make efficient use of the available radio spectrum resources.
The topology-based static channel assignment solutions determine the channel setting based on the number of interfering links, but it is traffic load rather than topology that causes interference. If there is no traffic going through a link, the link will not induce any interference to other links. As a result, this type of solutions works well when the load on each link is almost equal, but performs poor when the link load is highly unbalanced. As the traffic of wireless mesh networks is usually highly unbalanced (the links near the gateway may undergo much more traffics than other links), such solutions are not well applicable in wireless mesh networks.
The JCAR static channel assignment solutions assume both the topology and end-to-end traffic pattern are stable, while in some cases the end-to-end traffic may not be stable even in the long term. Previous measurement work shows that the traffics on both local area networks and wide area networks are highly self-similar, which means that the traffic sequence measured at a small time scale (such as every second) shows a similar burst pattern to the traffic sequence measured at a large time scale (such as every hour). As a result, the sequences of traffic cannot be considered stable even on a large time scale. Furthermore, the JCAR solutions result in the static routing configuration in the network so it cannot dynamically react to the failures of nodes and links, while such failures in wireless networks inherently happen more frequently than in wired networks. Although we can revise existing routing protocols so that it can use the static routing as the default configuration and search for new paths in the case of node/link failures, the revision done on one routing protocol cannot be applicable to other routing protocols.